from RandomList import GetRandomList

# 二分插入排序: 用二分搜索选择插入位置
def binary_insertion_sort(arr):
    num = len(arr)
    for i in range(1, num):
        left = 0
        right = i - 1
        temp = arr[i]
        while left <= right:
            mid = (left + right)//2
            if arr[mid] < temp:
                left = mid + 1
            else:
                right = mid - 1
        j = i - 1
        while j >= left:
            arr[j + 1] = arr[j]
            j -= 1
        arr[left] = temp
    return arr


if __name__ == "__main__":
    Arr = GetRandomList(100)
    Arr = binary_insertion_sort(Arr)
    print(Arr)